import java.util.*;

public class Solution952 {

    static class BingChaJi{
        int[] b;
        int[] size;

        public BingChaJi(int n){
            b=new int[n];
            size=new int[n];
            for (int i=0;i<n;i++){
                b[i]=i;
            }
        }

        public void union(int x,int y){
            int p=find(x),q=find(y);
            if (p!=q){
                b[q]=p;
                size[p]+=size[q];
            }
        }

        private int find(int x) {
            return b[x]==x?x:(b[x]=find(b[x]));
        }
    }

    public int largestComponentSize(int[] nums) {
        boolean[] f=new boolean[100001];
        Arrays.fill(f,true);
        for (int i=2;i<=100000;i++){
            if (f[i]){
                for (int j=2;i*j<=100000;j++){
                    f[i*j]=false;
                }
            }
        }
        int id=0;
        Map<Integer,Integer> map=new HashMap<>();
        for (int i=2;i<=100000;i++){
            if (f[i]){
                map.put(i,id);
                id++;
            }
        }
        BingChaJi bingChaJi=new BingChaJi(id);
        for (int num : nums) {
            if (num==1){
                continue;
            }
            List<Integer> list=new ArrayList<>();
            for (int j=2;j*j<=num;j++){
                if (num%j==0){
                    list.add(j);
                    while (num%j==0){
                        num/=j;
                    }
                }
            }
            if (num!=1){
                list.add(num);
            }
            bingChaJi.size[bingChaJi.find(map.get(list.get(0)))]++;
            for (int j=1;j<list.size();j++){
                bingChaJi.union(map.get(list.get(0)),map.get(list.get(j)));
            }
        }
        int ans=0;
        for (int i=0;i<id;i++){
            ans=Math.max(ans,bingChaJi.size[bingChaJi.find(i)]);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution952().largestComponentSize(new int[]{20,50,9,63}));
    }
}
